Expansion and search in networks.
Borrowing from concepts in expander graphs, we study the expansion properties of real-world, complex networks (e.g. social networks, unstructuredpeer-to-peeror P2P networks) and the extent to which these properties can be exploited to understand and address the problem of decentralized search. We first produce samples that concisely capture the overall expansion properties of an entire network, which we collectively refer to as the expansion signature. Using these signatures, we find a correspondence between the magnitude of maximum expansion and the extent to which a network can be efficiently searched. We further find evidence that standard graph-theoretic measures, such as average path length, fail to fully explain the level of“searchability”or ease of information diffusion and dissemination in a network. Finally, we demonstrate that this high expansion can be leveraged to facilitate decentralized search in networks and show that an expansion-based search strategy outperforms typical search methods.
Online Sampling of High Centrality Individuals in Social Networks.

Session Introduction.

Discovering Kinship through Small Subsets.

Discovering Kinship through Small Subsets.

Sampling community structure.

Sampling community structure.

Expansion and Search in Networks
Borrowing from concepts in expander graphs, we study the expansion properties of real-world, complex networks (e.g. social networks, unstructuredpeer-to-peeror P2P networks) and the extent to which these properties can be exploited to understand and address the problem of decentralized search. We first produce samples that concisely capture the overall expansion properties of an entire network, which we collectively refer to as the expansion signature. Using these signatures, we find a correspondence between the magnitude of maximum expansion and the extent to which a network can be efficiently searched. We further find evidence that standard graph-theoretic measures, such as average path length, fail to fully explain the level of“searchability”or ease of information diffusion and dissemination in a network. Finally, we demonstrate that this high expansion can be leveraged to facilitate decentralized search in networks and show that an expansion-based search strategy outperforms typical search methods.
New Optimization Model and Algorithm for Sibling Reconstruction from Genetic Markers.


Combinatorial Reconstruction of Half%2DSibling Groups from Microsatellite Data.
While full sibling group reconstruction from microsatellite data is a well studied problem, reconstruction of half sibling groups is much less studied, theoretically challenging, and a computationally demanding problem. In this paper, we present a formulation of the half-sibling reconstruction problem and prove it APX-hardness. We also present exact solutions for this formulation and develop heuristics. Using biological and synthetic datasets we present experimental results and compare them with the leading alternative software COLONY. We show that our results are competitive and allow half-sibling group reconstruction in the presence of polygamy, which is prevalent in nature. 1.

On Approximating an Implicit Cover Problem in Biology.

Inferring the Maximum Likelihood Hierarchy in Social Networks.

Constant%2Dfactor approximation algorithms for identifying dynamic communities.
We propose two approximation algorithms for identifying communities in dynamic social networks. Communities are intuitively characterized as “unusually densely knit ” subsets of a social network. This notion becomes more problematic if the social interactions change over time. Aggregating social networks over time can radically misrepresent the existing and changing community structure. Recently, we have proposed an optimization-based framework for modeling dynamic community structure. Also, we have proposed an algorithm for finding such structure based on maximum weight bipartite matching. In this paper, we analyze its performance guarantee for a special case where all actors can be observed at all times. In such instances, we show that the algorithm is a small constant factor approximation of the optimum. We use a similar idea to design an approximation algorithm for the general case where some individuals are possibly unobserved at times, and to show that the approximation factor increases twofold but remains a constant regardless of the input size. This is the first algorithm for inferring communities in dynamic networks with a provable approximation guarantee. We demonstrate the general algorithm on real data sets. The results confirm the efficiency and effectiveness of the algorithm in identifying dynamic communities.
Session Introduction.

On approximating four covering and packing problems.
In this paper, we consider approximability issues of the following four problems: triangle packing, full sibling reconstruction, maximum profit coverage and 2-coverage. All of them are generalized or specialized versions of set-cover and have applications in biology ranging from fullsibling reconstructions in wild populations to biomolecular clusterings; however, as this paper shows, their approximability properties differ considerably. Our inapproximability constant for the triangle packing problem improves upon the previous results in [13, 16]; this is done by directly transforming the inapproximability gap of H˚astad for the problem of maximizing the number of satisfied equations for a set of equations over GF(2) [23] and is interesting in its own right. Our approximability results on the full siblings reconstruction problems answers questions posed by Berger-Wolf et al. [4, 5] and our results on the maximum profit coverage problem provides almost matching upper and lower bounds on the approximation ratio, answering a question posed by Hassin and Or [22]. ∗ Supported by NSF grant IIS-0612044. † Supported by NSF grants DBI-0543365, IIS-0612044 and IIS-0346973.
Mining Periodic Behavior in Dynamic Social Networks.

Mining Periodic Behavior in Dynamic Social Networks.

The Impact of Structural Changes on Predictions of Diffusion in Networks.

Finding Spread Blockers in Dynamic Networks.
Abstract. Social interactions are conduits for various processes spreading through a population, from rumors and opinions to behaviors and diseases. In the context of the spread of a disease or undesirable behavior, it is important to identify blockers: individuals that are most effective in stopping or slowing down the spread of a process through the population. This problem has so far resisted systematic algorithmic solutions. In an effort to formulate practical solutions, in this paper we ask: Are there structural network measures that are indicative of the best blockers in dynamic social networks? Our contribution is two-fold. First, we extend standard structural network measures to dynamic networks. Second, we compare the blocking ability of individuals in the order of ranking by the new dynamic measures. We found that overall, simple ranking according to a node’s static degree, or the dynamic version of a node’s degree, performed consistently well. Surprisingly the dynamic clustering coefficient seems to be a good indicator, while its static version performs worse than the random ranking. This provides simple practical and locally computable algorithms for identifying key blockers in a network. 1
Structure Prediction in Temporal Networks using Frequent Subgraphs.
Abstract — There are several types of processes which can be modeled explicitly by recording the interactions between a set of actors over time. In such applications, a common objective is, given a series of observations, to predict exactly when certain interactions will occur in the future. We present a representation for this type of temporal data and a generic, adaptive algorithm to predict the pattern of interactions at any arbitrary point in the future. We test our algorithm on predicting patterns in email logs, correlations between stock closing prices, and social grouping in herds of Plains zebra. Our algorithm averages over 85 % accuracy in predicting a set of interactions at any unseen timestep. To the best of our knowledge, this is the first algorithm that predicts interactions at the finest possible time grain. I.
Reconstructing sibling relationships in wild populations.
I do not believe that the accident of birth makes people sisters and brothers. It makes them siblings. Gives them mutuality of parentage.. – Maya Angelou New technologies for collecting genotypic data from natural populations open the possibilities of investigating many fundamental biological phenomena, including behavior, mating systems, heritabilities of adaptive traits, kin selection, and dispersal patterns. The power and potential of genotypic information often rests in the ability to reconstruct genealogical relationships among individuals. These relationships include parentage, full and half-sibships, and higher order aspects of pedigrees. Some areas of genealogical inference, such as parentage, have been studied extensively. Although methods for pedigree inference and kinship analysis exist, most make assumptions that do not hold for wild populations of animals and plants. In this chapter, we focus on the full sibling relationship and first review existing methods for full sibship reconstructions from microsatellite genetic markers. We then describe our new combinatorial methods for sibling reconstruction based on simple Mendelian laws and its extension even in the presence of errors in the data. We also describe a generic consensus method for combining sibling reconstruction results from other methods. We present experimental comparison of the best existing approaches on both biological and simulated data. We discuss relative merits and drawbacks of existing methods and suggest a practical approach for reconstructing sibling relationships in wild populations. 1
A framework for community identification in dynamic social networks.

A framework for analysis of dynamic social networks.
Finding patterns of social interaction within a population has wide-ranging applications including: disease modeling, cultural and information transmission, and behavioral ecology. Social interactions are often modeled with networks. A key characteristic of social interactions is their continual change. However, most past analyses of social networks are essentially static in that all information about the time that social interactions take place is discarded. In this paper, we propose a new mathematical and computational framework that enables analysis of dynamic social networks and that explicitly makes use of information about when social interactions occur.
Online Consensus and Agreement of Phylogenetic Trees.
Abstract. Computational heuristics are the primary methods for reconstruction of phylogenetic trees on large datasets. Most large-scale phylogenetic analyses produce numerous trees that are equivalent for some optimization criteria. Even using the best heuristics, it takes significant amount of time to obtain optimal trees in simulation experiments. When biological data are used, the score of the optimal tree is not known. As a result, the heuristics are either run for a fixed (long) period of time, or until some measure of a lack of improvement is achieved. It is unclear, though, what is a good criterion for measuring this lack of improvement. However, often it is useful to represent the collection of best trees so far in a compact way to allow scientists to monitor the reconstruction progress. Consensus and agreement trees are common such representations. Using existing static algorithms to produce these trees increases an already lengthy computational time substantially. In this paper we present efficient online algorithms for computing strict and majority consensi and the maximum agreement subtree. 1
Sharp Bounds for Bandwidth of Clique Products


Index assignment for multichannel communication under failure.


Optimal Multichannel Communication Under Failure.
Tanya Y. Berger-Wolf    Edward M. Reingold  y  October 19, 1998  Abstract  We consider the problem of communication over multiple channels in which channels can fail and the information sent over those channels is lost. The goal is to recover as much of the original information as possible while having as little redundancy as possible. We analyze the problem of designing an encoding that minimizes the decoding error in case of channel failure; we give tight lower bounds and an optimal algorithm.  1 Problem Statement  Consider sending lg m bits of information over k independent channels. We want to partition the lg m bits into k subsets so that if all k subsets are received, the original information can be completely reconstructed. A trivial solution would be to send k blocks of (lg m)=k bits each; if any block fails to arrive, that part of the information is lost. Alternatively, we could send k complete copies, a total of k  lg m bits, so that even if all but one of the channels f...
